(define (amb/analyze exp)
  (let ([dispatch-fn (get dispatch-tt 'amb (list-tag exp))])
    (cond
     [(self-evaluating? exp)
      (amb/self-evaluating exp)]
     [(quoted? exp)
      (amb/quoted exp)]
     [(variable? exp)
      (amb/variable exp)]
     [(procedure? dispatch-fn)
      (dispatch-fn exp)]
     [(application? exp)
      (amb/application exp)]
     [else
      (error "Unknown expression type: ANALYZE" exp)])))

(define (amb/choices exp) (cdr exp))
(define (ambeval exp env succeed fail)
  "The top-level procedure ambeval analyzes the given expression and applies the
resulting execution procedure to the given environment, together with two given
continuations"
  ((amb/analyze exp) env succeed fail))



(define (amb/self-evaluating exp)
  (λ (env succeed fail)
    (succeed exp fail)))

(define (amb/quoted exp)
  (let ([qval (text-of-quotation exp)])
    (λ (env succeed fail)
      (succeed qval fail))))

(define (amb/variable exp)
  (λ (env succeed fail)
    (succeed (lookup-variable-value exp env) fail)))

(define (amb/analyze-lambda exp)
  (let ((vars (lambda-parameters exp))
        (bproc (amb/analyze-sequence
                (lambda-body exp))))
    (λ (env succeed fail)
      (succeed (make-procedure vars bproc env) fail))))

(define (amb/analyze-if exp)
  "The execution procedure generated by amb/analyze-if invokes the predicate execution
procedure predicate with a success continuation that checks whether the predicate
value is true and goes on to execute either the consequent or the alternative.
If the execution of predicate fails, the original failure continuation for the if
expression is called."
  (let ((predicate (amb/analyze (if-predicate exp)))
        (consequent (amb/analyze (if-consequent exp)))
        (alternative (amb/analyze (if-alternative exp))))
    (λ (env succeed fail)
      (predicate
       env
       ;; success: evaluate the pred `pred-value'
       (λ (pred-value fail2)
         (if (true? pred-value)
             (consequent env succeed fail2)
             (alternative env succeed fail2)))
       ;; failure
       fail))))

(define (amb/analyze-sequence exps)
"Sequences are also handled in the same way as in the previous evaluator,
except for the machinations in the subprocedure sequentially that are required
for passing the continuations. Namely, to sequentially execute a and then b, we
call a with a success continuation that calls b. "
  (define (sequentially a b)
    (lambda (env succeed fail)
      (a env
         ;; success
         (lambda (a-value fail2)
           (b env succeed fail2))
         ;; failure
         fail)))

  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc (car rest-procs))
              (cdr rest-procs))))

  (let ((procs (map amb/analyze exps)))
    (if (null? procs)
        (error "Empty sequence: ANALYZE"))
    (loop (car procs) (cdr procs))))

(define (amb/analyze-definition exp)
  "definition-value execution procedure vproc is called with the environment, a
success continuation, and the failure continuation. If the execution of vproc
succeeds, obtaining a value val for the defined variable, the variable is
defined and the success is propagated"
  (let ((var   (definition-variable exp))
        (vproc (amb/analyze (definition-value exp))))
    (lambda (env succeed fail)
      (vproc env
             ;; success
             (λ (val fail2)
               (define-variable! var val env)
               (succeed 'ok fail2))
             ;; failure
             fail))))

(define (amb/analyze-assignment exp)
  "The execution procedure for assignments starts out like the one for
definitions. It first attempts to obtain the new value to be assigned to the
variable. If this evaluation of vproc fails, the assignment fails."
  (let ([var (assignment-variable exp)]
        [vproc (amb/analyze (assignment-value exp))])
    (lambda (env succeed fail)
      (vproc env
             ;; vproc's success continuation at saves the old value of the
             ;; variable before assigning the new value to the variable and
             ;; proceeding from the assignment.
             (λ (val fail2) ; *1*
               (let ([old-value (lookup-variable-value var env)])
                 (set-variable-value! var val env)
                 (succeed
                  'ok
                  ;; a failure restores the old value of the variable before
                  ;; continuing the failure
                  (λ ()    ; *2*
                    (set-variable-value! var old-value env)
                    (fail2)))))
             fail))))

(define (amb/application exp)
  (let ([fn (amb/analyze (operator exp))]
        [aprocs (map amb/analyze (operands exp))])
    (lambda (env succeed fail)
      (fn env
             ;; success
             (λ (proc fail2)
               (get-args aprocs
                         env
                         (λ (args fail3)
                           (amb/apply proc args succeed fail3))
                         fail2))
             ;; fail
             fail))))

(define (get-args aprocs env succeed fail)
  (if (null? aprocs) (succeed '() fail)
      ((car aprocs)
       env
       ;; success continuation for this aproc
       (lambda (arg fail2)
         (get-args
          (cdr aprocs)
          env
          ;; success continuation for recursive call to get-args
          (lambda (args fail3)
            (succeed (cons arg args)
                     fail3))
          fail2))
       fail)))

(define (amb/apply proc args succeed fail)
  "The actual procedure application, which is performed by amb/apply, is
accomplished in the same way as for the ordinary evaluator, except for the need
to manage the continuations."
  (cond ((primitive-procedure? proc)
         (succeed (apply-primitive-procedure proc args) fail))
        ((compound-procedure? proc)
         ((procedure-body proc)
          (extend-environment
           (procedure-parameters proc)
           args
           (procedure-environment proc))
          succeed
          fail))
        (else (error "Unknown procedure type: EXECUTE-APPLICATION" proc))))


(define (amb/analyze-amb exp)
  "The amb special form is the key element in the nondeterministic language.
Here we see the essence of the interpretation process and the reason for keeping
track of the continuations. The execution procedure for amb defines a loop
try-next that cycles through the execution procedures for all the possible
values of the amb expression. Each execution procedure is called with a failure
continuation that will try the next one. When there are no more alternatives to
try, the entire amb expression fails."
  (let ((cprocs (map amb/analyze (amb/choices exp))))
    (lambda (env succeed fail)
      (define (try-next choices)
        (if (null? choices)
            (fail)
            ((car choices)
             env
             succeed
             (lambda ()
               (try-next (cdr choices))))))
      (try-next cprocs))))

(define (amb/driver-loop)
  (define (internal-loop try-again)
    (prompt-for-input ";;; Amb/Eval input:")
    (let ((input (read)))
      (if (eq? input 'nx) (try-again)
          (begin
            (newline)
            (display ";;; Starting a new problem ")
            (ambeval
             input
             the-global-environment
             ;; ambeval success
             (lambda (val next-alternative)
               (announce-output ";;; Amb/Eval value:")
               (user-print val)
               (internal-loop next-alternative))
             ;; ambeval failure
             (lambda ()
               (announce-output
                ";;; There are no more values of")
               (user-print input)
               (amb/driver-loop)))))))
  (internal-loop
   (lambda ()
     (newline)
     (display
      ";;; There is no current problem")
     (amb/driver-loop))))
